// 7.16 试对邻接表存储结构重做7.15题。
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\6Graph\1_Adjacency_lIST\Adjacency_LIST.h"
// INSERT VEX
void fun_7_15_1(ALGraph &G, Node n)
{
    G.node_num++;
    G.AdjList[G.node_num - 1] = n;
}
// INSERT ARC
void fun_7_15_2(ALGraph &G, ArcNode *a, Node n)
{
    int i = 0;
    while (i < G.node_num && G.AdjList[i].data != n.data)
    {
        i++;
    }
    if (i < G.node_num)
    {
        ArcNode *t = G.AdjList[i].frist;
        a->next = t;
        G.AdjList[i].frist = a;
    }
    // 有向图插入完毕
    // 无向图的双向插入
    int j = a->node_num;
    ArcNode *t = G.AdjList[j].frist;
    ArcNode *copy_a = (ArcNode *)malloc(sizeof(ArcNode));
    copy_a->node_num = i;
    copy_a->next = t;
    G.AdjList[j].frist = copy_a;
}
// DELETE VEX
void fun_7_15_3(ALGraph &G, Node n)
{
    int i = 0;
    while (i < G.node_num && G.AdjList[i].data != n.data)
    {
        i++;
    }

    if (i < G.node_num)
    { // delete correlative arc
        for (int j = 0; j < G.node_num; j++)
        {
            ArcNode *pre = G.AdjList[j].frist;
            if (pre)
            {
                if (pre->node_num == i)
                {
                    G.AdjList[j].frist = pre->next;
                }
                else
                {
                    ArcNode *t = pre->next;
                    while (t)
                    {
                        if (t->node_num == i)
                        {
                            pre->next = t->next;
                        }
                        pre = t;
                        t = t->next;
                    }
                }
            }
        }
        G.AdjList[i] = G.AdjList[G.node_num--];
    }
}
// DELETE ARC
void fun_7_15_4(ALGraph &G, ArcNode *a, Node n)
{
    Node s = G.AdjList[a->node_num];
    int i = 0;
    while (i < G.node_num && G.AdjList[i].data != n.data)
    {
        i++;
    }
    // 释放s节点与n有关的边
    ArcNode *pre = s.frist;
    if (pre)
    {
        if (pre->node_num == i)
        {
            s.frist = pre->next;
        }
        else
        {
            ArcNode *t = pre->next;
            while (t)
            {
                if (t->node_num == i)
                {
                    pre->next = t->next;
                }
                pre = t;
                t = t->next;
            }
        }
    }
    // 释放n节点与s有关的边
    pre = G.AdjList[i].frist;
    if (pre)
    {
        if (pre->node_num == a->node_num)
        {
            G.AdjList[i].frist = pre->next;
        }
        else
        {
            ArcNode *t = pre->next;
            while (t)
            {
                if (t->node_num == a->node_num)
                {
                    pre->next = t->next;
                }
                pre = t;
                t = t->next;
            }
        }
    }
}

int main()
{
    /*******************code*******************/
    ALGraph G;
    create_G(G);
    Node n;
    n.data = 6;
    n.weight = 0;
    n.frist = NULL;
    fun_7_15_1(G, n);
    ArcNode *a = (ArcNode *)malloc(sizeof(ArcNode));
    a->node_num = 0;
    a->next = NULL;
    fun_7_15_2(G, a, n);
    visit_G(G);
    fun_7_15_3(G, n);
    visit_G(G);
    ArcNode *a1 = (ArcNode *)malloc(sizeof(ArcNode));
    a1->node_num = 3;
    a1->next = NULL;
    Node n1;
    n1.data = 1;
    n1.weight = 0;
    n1.frist = NULL;
    fun_7_15_4(G, a1, n1);
    visit_G(G);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
